package dataStructAlgotiyhm;

/**
 * https://blog.csdn.net/ChinaDragon10/article/details/109442093
 * 队列在线程池等有限资源池中的应用
 * <p>
 * 线程池相关文章 https://so.csdn.net/so/search?q=%E7%BA%BF%E7%A8%8B%E6%B1%A0&spm=1001.2101.3001.7020
 * <p>
 * <p>
 * 队列（queue）
 * 栈只支持两个基本操作：入栈 push()和出栈 pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。
 * 队列跟栈一样，也是一种操作受限的线性表数据结构。
 * <p>
 * 队列的概念很好理解，基本操作也很容易掌握。作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，
 * 比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。
 * <p>
 * 跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。
 */

//用数组实现的队列
public class ArrayQueue {
    // 数组：items，数组大小：n
    private String[] items;
    private int n = 0;

    // head表示队头下标，tail表示队尾下标
    private int head = 0;
    private int tail = 0;

    // 申请一个大小为capacity的数组
    public ArrayQueue(int capacity) {
        items = new String[capacity];
        n = capacity;
    }

    //入列
    public boolean enqueue(String item) {
        // 如果tail == n 表示队列已经满了
        if (tail == n) {
            //tail ==n && head==0，表示整个队列都占满了
            if (head == 0) return false;

            // 数据搬移
            for (int i = head; i < tail; i++) {
                items[i - head] = items[i];
            }

            // 搬移完之后重新更新head和tail
            tail -= head;
            head = 0;

        }

        items[tail] = item;
        ++tail;
        return true;
    }

    // 出队
    public String dequeue() {
        //如果head == tail 表示队列为空
        if (head == tail) return null;

        String ret = items[head];
        ++head;
        return ret;
    }


}
